#include <bits/stdc++.h>
using namespace std;

/*
812. 最大三角形面积
已解答
简单
相关标签
premium lock icon
相关企业
给你一个由 X-Y 平面上的点组成的数组 points ，其中 points[i] = [xi, yi] 。从其中取任意三个不同的点组成三角形，返回能组成的最大三角形的面积。与真实值误差在 10-5 内的答案将会视为正确答案。

 

示例 1：


输入：points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
输出：2.00000
解释：输入中的 5 个点如上图所示，红色的三角形面积最大。
示例 2：

输入：points = [[1,0],[0,0],[0,1]]
输出：0.50000
 

提示：

3 <= points.length <= 50
-50 <= xi, yi <= 50
给出的所有点 互不相同
*/

// 法一
class Solution {
public:
    double largestTriangleArea(vector<vector<int>>& points) {
        int n = points.size();
        double maxArea = 0.0;
        
        // 遍历所有可能的三个不同点的组合
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                for (int k = j + 1; k < n; ++k) {
                    // 取出三个点的坐标
                    int x1 = points[i][0], y1 = points[i][1];
                    int x2 = points[j][0], y2 = points[j][1];
                    int x3 = points[k][0], y3 = points[k][1];
                    
                    // 利用向量叉积公式计算三角形面积：0.5 * | (x2-x1)(y3-y1) - (y2-y1)(x3-x1) |
                    // 叉积的绝对值等于以两向量为邻边的平行四边形面积，三角形面积是其一半
                    double area = 0.5 * abs( (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) );
                    
                    // 更新最大面积
                    if (area > maxArea) {
                        maxArea = area;
                    }
                }
            }
        }
        
        return maxArea;
    }
};

// 法二
class Solution {
public:
    double largestTriangleArea(vector<vector<int>>& points) {
        int n = points.size();
        // 边界情况：点数量≤3，直接计算
        if (n <= 3) {
            return calculateMaxArea(points);
        }
        
        // 1. 先求点集的凸包（过滤内点，减少后续计算量）
        vector<vector<int>> convexHull = getConvexHull(points);
        // 2. 仅对凸包上的点计算最大面积
        return calculateMaxArea(convexHull);
    }

private:
    // 计算点集内所有三点组合的最大面积（核心公式不变，仅作用于筛选后的点集）
    double calculateMaxArea(const vector<vector<int>>& points) {
        int m = points.size();
        double maxArea = 0.0;
        // 三层循环遍历凸包上的所有三点组合（i<j<k避免重复）
        for (int i = 0; i < m; ++i) {
            int x1 = points[i][0], y1 = points[i][1]; // 提前缓存坐标，减少索引访问
            for (int j = i + 1; j < m; ++j) {
                int x2 = points[j][0], y2 = points[j][1];
                for (int k = j + 1; k < m; ++k) {
                    int x3 = points[k][0], y3 = points[k][1];
                    // 叉积公式计算面积：0.5 * |(x2-x1)(y3-y1) - (y2-y1)(x3-x1)|
                    double area = 0.5 * abs((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1));
                    maxArea = max(maxArea, area);
                }
            }
        }
        return maxArea;
    }

    // 凸包算法（Andrew算法，O(n log n)，高效筛选凸包点）
    vector<vector<int>> getConvexHull(vector<vector<int>>& points) {
        // 步骤1：按x坐标排序（x相同按y坐标），确定排序基准
        sort(points.begin(), points.end(), [](const auto& a, const auto& b) {
            return a[0] != b[0] ? a[0] < b[0] : a[1] < b[1];
        });
        
        vector<vector<int>> hull;
        int n = points.size();
        // 步骤2：构建下凸壳（从左到右，保证逆时针转向）
        for (int i = 0; i < n; ++i) {
            // 移除凹点：当前点与前两点构成顺时针转向时，删除中间点
            while (hull.size() >= 2 && cross(hull[hull.size()-2], hull.back(), points[i]) <= 0) {
                hull.pop_back();
            }
            hull.push_back(points[i]);
        }
        
        // 步骤3：构建上凸壳（从右到左，保证逆时针转向），注意跳过已加入的最后一个点
        int lowerSize = hull.size();
        for (int i = n - 2; i >= 0; --i) {
            while (hull.size() > lowerSize && cross(hull[hull.size()-2], hull.back(), points[i]) <= 0) {
                hull.pop_back();
            }
            hull.push_back(points[i]);
        }
        
        // 步骤4：删除重复的起点（凸包是闭合的，最后一个点与第一个点相同）
        hull.pop_back();
        return hull;
    }

    // 计算叉积：判断三点a→b→c的转向（核心辅助函数）
    // 叉积 >0：逆时针；=0：共线；<0：顺时针
    int cross(const vector<int>& a, const vector<int>& b, const vector<int>& c) {
        return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]);
    }
};